// 2025/3/21
// https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked
// 搜索二维矩阵

class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int left = 0, right = matrix.size() - 1;
            int mid = (left + right) / 2;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(matrix[mid][0] > target)
                    right = mid - 1;
                else if(matrix[mid][0] < target)
                    left = mid + 1;
                else
                    return true;
            }
            int x = (matrix[mid][0] > target && mid > 0) ? mid - 1 : mid;
            left = 0, right = matrix[0].size() - 1;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(matrix[x][mid] > target)
                    right = mid - 1;
                else if(matrix[x][mid] < target)
                    left = mid + 1;
                else
                    return true;
            }
            return false;
        }
    };